/*
 * @lc app=leetcode.cn id=319 lang=cpp
 *
 * [319] 灯泡开关
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    /**
     * @brief 获取低n位设置为1的值
     * 
     * @param n 
     * @return int 
     */
    int set1(int n)
    {
        int light = 0;
        for (int i = 0; i < n; i++)
        {
            light |= 1 << i;
        }
        return light;
    }

    /**
     * @brief 判断值light的低n位有几个1
     * 
     * @param light 
     * @param n 
     * @return int 
     */
    int get1(int light, int n)
    {
        int ans = 0;
        for(int i = 0; i < n && light; i++)
        {
            if(light & 1) ans++;
            light >>= 1;
        }
        return ans;
    }

    /**
     * @brief 对light的低n位每隔step取一次反
     * 
     * @param light 
     * @param n 
     * @param step 
     * @return int 
     */
    int get_not(int light, int n, int step)
    {
        for(int i = 0; i <= n; i += step)
        {
            if(i % step == 0 && i)
            {
                int tmp = light & (1 << (i-1));//获取第 低 i 位 的值
                if(tmp)
                    light ^= tmp;//置为0
                else
                    light |= ((1 << (i-1)));//置为1
            }
        }
        return light;
    }

    int bulbSwitch(int n)
    {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 1;

        // n = 30;
        // int light = set1(n);
        // for (int j = 1; j < n; j++)
        // {
        //     printf("%d盏灯，经过%d轮后，亮着的灯有%d盏\n", j, j, get1(light, j));
        //     light = get_not(light, n, j + 1);
        //     // printf("0x%X\n", light);
        // }

        

        return sqrt(n);
    }
};

// int main()
// {
//     Solution().bulbSwitch(20);
//     return 0;
// }
// @lc code=end
